using namespace std;
#include<iostream>
#include<vector>
//class solution
//{
//public:
//	void QuickSort(vector<int>& nums,int left,int right)
//	{
//		if (left >= right) return;
//		int key = left;
//		int pre = left;
//		int cur = left + 1;
//		while (cur <= right)
//		{
//			if (nums[cur] < nums[key])
//			{
//				pre++;
//				swap(nums[cur], nums[pre]);
//				cur++;
//			}
//			else
//			{
//				cur++; 
//			}
//		 }
//		swap(nums[key], nums[pre]);
//		key = pre;
//		QuickSort(nums, left, key - 1);
//		QuickSort(nums, key + 1, right);
//	}
//};

//class solution
//{
//public:
//	void QuickSort(vector<int>& v1, int left, int right)
//	{
//		int key = left;
//		int pre = left;
//		int cur = left + 1;
//		while (cur < right)
//		{
//			if (v1[cur] < v1[key])
//			{
//				pre++;
//				swap(v1[pre], v1[cur]);
//				cur++;
//			}
//			else
//			{
//				cur++;
//			}
//		}
//
//	}
//};
 

//int main()
//{
//	vector<int> v1 = { 5,7,3,9,1 };
//	int n = v1.size();
//	solution sort_v1;
//	sort_v1.QuickSort(v1, 0, n - 1);
//	for (auto& elem : v1)
//	{
//		cout << elem << " ";
//	}
//	return 0;
//}


class Solution {
public:
    void duplicateZeros(vector<int>& arr)
    {
        int  prev = 0;
        int cur = 0;
        int n = arr.size();
        
         for (prev = 0; prev < n; prev++)
        {
            int end = n - 1;
            if (arr[prev] == 0)
            {
                while (end > prev)
                {
                    arr[end] = arr[end - 1];
                    end--;
                }
                if (prev <= n - 2)
                {
                    cur = prev + 1;
                }
                arr[cur] = arr[prev];
                prev++;
                if (prev > n - 1)
                {
                    break;
                }
            }
        }
    }
};


int main()
{
    vector<int> v1 = { 8,4,5,0,0,0,0,7 };
	Solution zero_v1;
	zero_v1.duplicateZeros(v1);
	for (auto& elem : v1)
	{
		cout << elem << " ";
	}
	return 0;
}